331. 验证二叉树的前序序列化

Similar Question

leading to the advanced question

Solution Tips

方案一: 入度和出度

栈方案的本质也是入度和出度

二叉树本来就是图，看成有向图，一条有向边带来一个入度和一个出度，二叉树的总入度等于总出度，也等于边数。即，遍历到最后，总入度肯定等于总出度

遍历过程中（null 也看作节点）：

• 根节点提供 2 个出度
• 根节点以外的真实节点，提供 2 个出度， 1 个入度
• null 节点提供 1 个入度

var isValidSerialization = function(preorder) {
    if (preorder == "#") { // 特例
        return true
    }
	
    let indegree = 0, outdegree = 0 // 初始 入度出度
    const nodes = preorder.split(",") // 转成数组
    
    for (let i = 0; i < nodes.length; i++) { // 遍历数组
        // 根节点, 没有入度, 只有出度, 需要特殊处理
        if (i == 0) { 
            if (nodes[i] == "#") { 
	            // #,#,1 这样的 是非法的
                return false
            }
            outdegree += 2 // 根节点  出度+2
            continue
        }
		
        if (nodes[i] == "#") {
	        // null节点，入度+1
			indegree += 1
		} else {
			// 非空节点 入度+1 出度+2
            indegree += 1  
            outdegree += 2
		}
		
        if (i != nodes.length - 1 && indegree >= outdegree) {
            //一直保持indegree<outdegree，直到最后才indegree==outdegree，做不到就false
            return false
        }
    }
    return indegree == outdegree // 最后肯定入度==出度
};

为什么遍历过程中出现 入度大于出度 就是不合法?

提供 1 个出度, 意味着可以挂载一个节点, 提供一个入度意味着消耗了一个挂载点

如果 入度 >= 出度, 意味着目前遍历到的节点当中消耗掉的挂载点已经大于了提供的挂载点, 所以肯定是不合法的